import java.util.*;
/**
 * 
 * 二叉树的后序遍历
 * 
 * 描述

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足 
1
≤
n
≤
100
 
1≤n≤100  ，二叉树节点的值满足 
1
≤
v
a
l
≤
100
 
1≤val≤100  ，树的各节点的值各不相同
 */
public class 二叉树的后序遍历 {
    
    public static void main(String[] args) {
        
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        int[] result = postorderTraversal(root);

        Arrays.stream(result).boxed().map(s -> s+"; ").forEach(System.out::print);
        System.out.println();

    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public static int[] postorderTraversal (TreeNode root) {
        // write code here

        if(null == root) return new int[] {};

        LinkedList<Integer> list = new LinkedList<>();
        afterForEach(root, list);
        
        int[] result = new int[list.size()];

        for(int i=0; i<list.size(); i++){
            result[i] = list.get(i);
        }


        return result;
    }

    private static void afterForEach(TreeNode node, LinkedList list){

        if(null!=node){

            afterForEach(node.left, list);
            list.add(node.val);
            afterForEach(node.right, list);

        }
    }
}
